/**
 * @file KNN.h
 * @author enemy1205 (enemy1205@qq.com)
 * @brief KNN算法头文件 , 在一组元素中找到输入元素所属类别
 * @date 2021-09-24
 */
#pragma once

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>

using namespace std;

class KNN {
public:
    //测试案例
    void test_knn();
    //默认构造
    KNN() = default;
    //给定数据运行
    void run(vector<vector<double>> &, vector<double> &, const int &);
};

class Math {
public:
    //计算方差
    static double getVariance(const vector<pair<vector<double>, uint> >::iterator &,
                       const vector<pair<vector<double>, uint> >::iterator &,
                       const uint &);
    //计算k伟距离
    static double getDistance(const vector<double>&,const vector<double> &);
};

class TreeNode {
public:
    //构造节点
    TreeNode(const vector<double> &, const uint &, const uint &);
    //获得坐标
    auto getCoordinate() const { return coordinate; }
    //获得维度
    uint getAxis() const { return axis; }
    //获得序号
    uint getIndex() const { return index; }
    //获得左节点
    TreeNode *getLchild() const { return lchild; }
    //获得右节点
    TreeNode *getRchild() const { return rchild; }
    //设置左节点
    void setLchild(TreeNode *t) { lchild = t; }
    //设置右节点
    void setRchild(TreeNode *t) { rchild = t; }

private:
    vector<double> coordinate;//节点数据(坐标值)
    uint axis;//子节点分类依据维度
    uint index;//节点编号,方便下标访问
    TreeNode *lchild, *rchild;//左右子节点
};

class KdTree {
public:
    //利用数据显示构造
    explicit KdTree(const vector<vector<double>> &);
    //构造KdTree
    TreeNode *buildKdTree(const vector<pair<vector<double>, uint> >::iterator &l,
                          const vector<pair<vector<double>, uint> >::iterator &r);
    //寻找所属子节点并保存路径
    void findPath(vector<TreeNode *> &path, TreeNode *t, const vector<double> &P) const;
    //删除KdTree
    void deleteKdTree(TreeNode *);
    //顺序插入
    static void orderInsert(vector<pair<uint, double> > &, const pair<uint, double> &) ;
    //寻找最近的k个点
    vector<pair<uint, double>> findKneighbor(const vector<double> &, const uint &) const;
    //析构
    ~KdTree() { delete this->tree; }

private:
    TreeNode *tree;//Kd树根节点
    uint dim;//维度
};